#include "Dwarf.Unmanaged.Mpi.h"

using namespace std;

// Branching information
BranchingInformation::BranchingInformation() {
	originalConstraintMap = NULL;
}

BranchingInformation::BranchingInformation(int cityCount, int *fixedBuffer, int *variableBuffer) {
	this->cityCount = cityCount;
	this->fixedBuffer = fixedBuffer;
	this->variableBuffer = variableBuffer;

    int n = cityCount;
	// FixedBuffer:
	//   0: ?
	//   1: # cycles
	//   2-3: lower bound
	//   4: # exclusions
	//   5: # child nodes
    CycleCount = fixedBuffer[1];
    LowerBound = ((__int64)fixedBuffer[2] << 32) + (unsigned)fixedBuffer[3];
    exclusionsCount = fixedBuffer[4];
    childCount = fixedBuffer[5];

	ToCities = fixedBuffer + 6;
	FromCities = fixedBuffer + 6 + n;
	u = fixedBuffer + 6 + 2 * n;
	v = fixedBuffer + 6 + 3 * n;
	ConstraintMap = fixedBuffer + 6 + 4 * n;

	// Make a copy of the initial constraint map.
	originalConstraintMap = new int[n];
	memcpy(originalConstraintMap, ConstraintMap, n * sizeof(int));

    Exclusions = variableBuffer;
    childToCities = variableBuffer + exclusionsCount;
    childFromCities = variableBuffer + exclusionsCount + childCount;
}

BranchingInformation::~BranchingInformation() {
	if (this->fixedBuffer != NULL)
		delete[] fixedBuffer;
	delete[] variableBuffer;
	if (originalConstraintMap != NULL)
		delete[] originalConstraintMap;
}

void BranchingInformation::Send(int destination) {
	int fixedSize = 6 + 5 * cityCount;
	MPI_Send(fixedBuffer, fixedSize, MPI_INT, destination, MpiBranchesMessage, MPI_COMM_WORLD);
	int length = exclusionsCount + 2 * childCount;
	MPI_Send(variableBuffer, length, MPI_INT, destination, MpiBranchesMessage, MPI_COMM_WORLD);
}

BranchingInformation* BranchingInformation::Receive(int cityCount, int source) {
    int n = cityCount;
	int fixedSize = 6 + 5 * cityCount;
	int* fixedBuffer = new int[fixedSize];
	MPI_Status status;
	MPI_Recv(fixedBuffer, fixedSize, MPI_INT, source, MpiBranchesMessage, MPI_COMM_WORLD, &status);
    
	int exclusionsCount = fixedBuffer[4];
    int childCount = fixedBuffer[5];
	int length = exclusionsCount + 2 * childCount;

	int* variableBuffer = new int[length];
	MPI_Recv(variableBuffer, length, MPI_INT, source, MpiBranchesMessage, MPI_COMM_WORLD, &status);
    return new BranchingInformation(cityCount, fixedBuffer, variableBuffer);
}

void BranchingInformation::Include(int* constraintMap, int from, int to) {
    constraintMap[from] = 1 + to;
}
void BranchingInformation::Exclude(int cityCount, int* constraintMap, int* exclusions, int& newExclusionsCount, int from, int to) {
    int index = constraintMap[from];
    if (index == 0) {
        // No constraints yet. Add this one at the end.
        constraintMap[from] = -1 - newExclusionsCount;
        exclusions[newExclusionsCount++] = to;
        exclusions[newExclusionsCount++] = -1;
    } else if (constraintMap[from] < 0) {
        // We have a constraint. Just insert this one at the front.
        for (int i = -1 - index; exclusions[i] != -1; i++) {
            if (exclusions[i] == to) {
                return;
            }
        }
		int offset = -1 - index;
		memcpy(exclusions + offset + 1, exclusions + offset, (newExclusionsCount - offset) * sizeof(int));
		exclusions[offset] = to;
		newExclusionsCount++;
        for (int i = 0; i < cityCount; i++) {
            if (i == from)
                continue;
            if (constraintMap[i] < index)
                constraintMap[i]--;
        }
    }
}

void BranchingInformation::GetChildConstraints(int childIndex, int* constraintMap, int*& exclusions, int& newExclusionsCount) {
	memcpy(constraintMap, originalConstraintMap, cityCount * sizeof(int));

    // Add inclusions
    for (int i = 0; i < childIndex; i++)
        Include(constraintMap, childFromCities[i], childToCities[i]);

	// Add exclusions
	exclusions = new int[exclusionsCount + 4];
	memcpy(exclusions, this->Exclusions, exclusionsCount * sizeof(int));
	
	newExclusionsCount = exclusionsCount;
    Exclude(cityCount, constraintMap, exclusions, newExclusionsCount, childFromCities[childIndex], childToCities[childIndex]);
    if (childIndex > 0) {
        Exclude(cityCount, constraintMap, exclusions, newExclusionsCount, ToCities[childIndex - 1], FromCities[0]);
		//newExclusionsCount = newExclusionsCount + 2;
    }
}

AssignmentProblem* BranchingInformation::GetProblem(int** distances, int childIndex, __int64 upperBound) { 
    int n = this->cityCount;
    int* constraintMap = this->ConstraintMap;
	int* exclusions;
	int newExclusionsLength;
    GetChildConstraints(childIndex, constraintMap, exclusions, newExclusionsLength);

	int fixedSize = 6 + 5 * n;
	int* buffer = new int[fixedSize];
	memcpy(buffer, fixedBuffer, fixedSize * sizeof(int));
	// Fixed buffer in assignment problem:
	//   2: exclusion length
	//   3: excluded row
	//   4-5: upper bound
	buffer[0] = 1;
	buffer[1] = 0;
    buffer[2] = newExclusionsLength;
    buffer[3] = GetExcludedRow(childIndex);
    buffer[4] = (int)(upperBound >> 32);
    buffer[5] = (int)(upperBound & 0xffffffff);
	return new AssignmentProblem(cityCount, distances, buffer, exclusions);
}

void BranchingInformation::SendProblem(int childIndex, __int64 upperBound, int destination) { 
    int n = cityCount;
    int* constraintMap = this->ConstraintMap;
	int* exclusions;
	int newExclusionsLength;
    GetChildConstraints(childIndex, constraintMap, exclusions, newExclusionsLength);

	int* buffer = fixedBuffer;
	int fixedSize = 6 + 5 * n;
	// Fixed buffer in assignment problem:
	//   2: exclusion length
	//   3: excluded row
	//   4-5: upper bound
	buffer[0] = 1;
    buffer[2] = newExclusionsLength;
    buffer[3] = GetExcludedRow(childIndex);
    buffer[4] = (int)(upperBound >> 32);
    buffer[5] = (int)(upperBound & 0xffffffff);
	MPI_Send(fixedBuffer, fixedSize, MPI_INT, destination, MpiProblemMessage, MPI_COMM_WORLD);
	MPI_Send(exclusions, newExclusionsLength, MPI_INT, destination, MpiProblemMessage, MPI_COMM_WORLD);
	delete[] exclusions;
}

// Assignment problem

AssignmentProblem::AssignmentProblem(int cityCount, int** distances) {
    this->cityCount = cityCount;
    this->distances = distances;

	this->fixedBuffer = new int[6 + 5 * cityCount];
    this->toCities = this->fixedBuffer + 6;
    this->fromCities = this->fixedBuffer + 6 + cityCount;
    this->u = this->fixedBuffer + 6 + 2 * cityCount;
    this->v = this->fixedBuffer + 6 + 3 * cityCount;
	this->constraintMap = this->fixedBuffer + 6 + 4 * cityCount;

    this->exclusions = NULL;
	this->exclusionsCount = 0;
	this->lowerBound = infinity;
	this->upperBound = infinity;
	this->patchedToCities = NULL;
    this->isRoot = true;
}

AssignmentProblem::AssignmentProblem(int cityCount, int** distances, int* theFixedBuffer, int* variableBuffer) {
    this->cityCount = cityCount;
    this->distances = distances;

	this->fixedBuffer = theFixedBuffer;

    this->toCities = this->fixedBuffer + 6;
    this->fromCities = this->fixedBuffer + 6 + cityCount;
    this->u = this->fixedBuffer + 6 + 2 * cityCount;
    this->v = this->fixedBuffer + 6 + 3 * cityCount;
	this->constraintMap = this->fixedBuffer + 6 + 4 * cityCount;

    this->exclusions = variableBuffer;
	this->exclusionsCount = 0;
	this->lowerBound = infinity;
	this->patchedToCities = NULL;
    this->isRoot = true;

	// Fixed buffer in assignment problem:
	//   2: exclusion length
	//   3: excluded row
	//   4-5: upper bound
    this->exclusionsLength = this->exclusionsCount = this->fixedBuffer[2];
	this->excludedRow = this->fixedBuffer[3];
    this->upperBound = ((__int64)this->fixedBuffer[4] << 32) + (unsigned)this->fixedBuffer[5];
    this->isRoot = false;
}

AssignmentProblem::~AssignmentProblem() {
	if (this->fixedBuffer != NULL)
		delete[] this->fixedBuffer;
	if (exclusions != NULL) {
		delete[] this->exclusions;
	}
}

AssignmentProblem* AssignmentProblem::Receive(int cityCount, int** distances, int source) {
    int n = cityCount;
	MPI_Status status;
	int fixedSize = 6 + 5 * n;
    int* fixedBuffer = new int[fixedSize];
	MPI_Recv(fixedBuffer, fixedSize, MPI_INT, source, MpiProblemMessage, MPI_COMM_WORLD, &status);
	// [0] == 0 -> empty problem
	if (fixedBuffer[0] == 0)
		return NULL;
    int exclusionsLength = fixedBuffer[2];
    int* variableBuffer = new int[exclusionsLength];
	MPI_Recv(variableBuffer, exclusionsLength, MPI_INT, source, MpiProblemMessage, MPI_COMM_WORLD, &status);
    return new AssignmentProblem(cityCount, distances, fixedBuffer, variableBuffer);
}

void AssignmentProblem::SendPrunedSolution(int destination) {
	int type = (int)PrunedSolution;
	MPI_Send(&type, 1, MPI_INT, destination, MpiSolutionMessage, MPI_COMM_WORLD);
}
void AssignmentProblem::SendExactSolution(int destination) {
    int n = cityCount;
    int length = 4 + n;
    int* buffer = new int[length];
	buffer[0] = (int)ExactSolution;
    buffer[2] = (int)(lowerBound >> 32);
    buffer[3] = (int)(lowerBound & 0xffffffff);
	memcpy(buffer + 4, toCities, n * sizeof(int));
	MPI_Send(buffer, length, MPI_INT, destination, MpiSolutionMessage, MPI_COMM_WORLD);
}
void AssignmentProblem::SendPatchedSolution(int destination) {
    int n = cityCount;
    int length = 4 + n;
    int* buffer = new int[length];
	buffer[0] = (int)PatchedSolution;
    buffer[2] = (int)(patchedValue >> 32);
    buffer[3] = (int)(patchedValue & 0xffffffff);
	memcpy(buffer + 4, patchedToCities, n * sizeof(int));
	MPI_Send(buffer, length, MPI_INT, destination, MpiSolutionMessage, MPI_COMM_WORLD);
}

void AssignmentProblem::GetCities(int* bestCities) {
	int* source = patchedToCities == NULL ? toCities : patchedToCities;
	memcpy(bestCities, source, cityCount * sizeof(int));
}

// 
// Solves the assignment problem and returns the total distance.
// 
__int64 AssignmentProblem::Solve() {
    if (lowerBound < infinity)
        return lowerBound;
    bool success;
    if (isRoot)
        success = SolveFromScratch();
    else 
        success = SolveIncremental();

    if (!success)
        return infinity;

    // Compute total distance.
    this->lowerBound = 0;
    for (int i = 0; i < cityCount; i++)
        lowerBound += u[i] + v[i];

    // Extract cycles
    ComputeCycles();
    if (cycles.size() == 1)
        patchedValue = lowerBound;
    return lowerBound;
}

bool AssignmentProblem::IsAllowed(int row, int column) {
    int value = constraintMap[row];
    return (row != column) && ((value == 0) ? (row != column) : IsAllowedConstraint(value, column));
}
bool AssignmentProblem::IsAllowedConstraint(int value, int column) {
    if (value > 0)
        // Include
        return column == (value - 1);
    else {
        // Exclude
        value = -1 - value;
        while (exclusions[value] >= 0) {
            if (exclusions[value] == column)
                return false;
            value++;
        }
        return true;
    }
}

void AssignmentProblem::Include(int from, int to) {
    this->constraintMap[from] = 1 + to;
}

void AssignmentProblem::Exclude(int from, int to) {
    int index = this->constraintMap[from];
    if (index == 0) {
        // No constraints yet. Add this one at the end.
        this->constraintMap[from] = -1 - this->exclusionsCount;
		exclusions[exclusionsCount++] = to;
		exclusions[exclusionsCount++] = -1;
    } else if (index < 0) {
        // We have a constraint. Just insert this one at the front.
        for (int i = -1 - index; this->exclusions[i] != -1; i++) {
            if (this->exclusions[i] == to) {
                //Console.WriteLine("Oops! This shouldn't happen!");
                return;
            }
        }
		int first = -1 - index;
		memmove(this->exclusions + (first + 1), this->exclusions + first, 
			(this->exclusionsCount - first) * sizeof(int));
		this->exclusions[first] = to;
        for (int i = 0; i < this->cityCount; i++) {
            if (i == from)
                continue;
            if (this->constraintMap[i] < index)
                this->constraintMap[i]--;
        }
    }
}

bool AssignmentProblem::SolveFromScratch() {

    // Label all cities as unassigned
    int assignedCities = 0;
    for (int i = 0; i < cityCount; i++) {
        toCities[i] = -1;
        fromCities[i] = -1;
		constraintMap[i] = 0;
		u[i] = 0;
		v[i] = 0;
    }

    // Find the smallest distance in each column.
    for (int column = 0; column < cityCount; column++) {
        // Find the i distance in the column.
        int minDistance = infinity;
        int minRow = -1;
        for (int row = 0; row < cityCount; row++) {
            if (!IsAllowed(row, column))
                continue;
            int distance = distances[row][column];
            if (distance < minDistance || (distance == minDistance && toCities[row] < 0)) {
                minRow = row;
                minDistance = distance;
            }
        }
        if (minRow < 0)
            return false;

        // This distance is the value of the dual variable of the column.
        v[column] = minDistance;

        // If the row is unassigned, we can assign it.
        if (toCities[minRow] < 0) {
            // Assign column to row minRow
            assignedCities++;
            fromCities[column] = minRow;
            toCities[minRow] = column;
            u[minRow] = 0;
        }
    }

    // Now look through unassigned rows, 
    // and see if they can be assigned.
    for (int row = 0; row < cityCount; row++) {
        if (toCities[row] >= 0)
            continue;

        int minReducedCost = infinity;
        int minColumn = -1;
        for (int column = 0; column < cityCount; column++) {
            if (!IsAllowed(row, column))
                continue;
            int reducedCost = distances[row][column] - v[column];
            if (reducedCost < minReducedCost
                || (reducedCost == minReducedCost && fromCities[column] < 0 && fromCities[minColumn] >= 0)) {
                minReducedCost = reducedCost;
                minColumn = column;
            }
        }

        if (minColumn < 0)
            return false;

        u[row] = minReducedCost;

        if (fromCities[minColumn] < 0) {
            // Assign minColumn to row i
            assignedCities++;
            toCities[row] = minColumn;
            fromCities[minColumn] = row;
        }
    }

    // For any remaining unassigned rows
    // we look for an augmenting path:
    if (assignedCities < cityCount) {
        AllocateAugmentingPathTemporaries();
        for (int row = 0; row < cityCount; row++) {
            if (toCities[row] >= 0)
                continue;
            FindAugmentingPath(row);
        }
        FreeAugmentingPathTemporaries();
    }
    return true;
}

bool AssignmentProblem::SolveIncremental() {
    int row = this->excludedRow;
    int column = toCities[row];
    fromCities[column] = -1;
    toCities[row] = -1;

    AllocateAugmentingPathTemporaries();
    FindAugmentingPath(row);
    FreeAugmentingPathTemporaries();
    return true;
}

void AssignmentProblem::AllocateAugmentingPathTemporaries() {
    pathOrigins = new int[cityCount];
    reducedCosts = new int[cityCount];
    labeledRow = new int[cityCount];
    unlabeledColumn = new int[cityCount];
}
void AssignmentProblem::FreeAugmentingPathTemporaries() {
    delete[] pathOrigins;
    delete[] reducedCosts;
    delete[] labeledRow;
    delete[] unlabeledColumn;
}

void AssignmentProblem::FindAugmentingPath(int row) {
    labeledRow[0] = row;
    for (int column = 0; column < cityCount; column++) {
        if (!IsAllowed(row, column))
            reducedCosts[column] = infinity;
        else
            reducedCosts[column] = distances[row][column] - u[row] - v[column];
        pathOrigins[column] = row;
        unlabeledColumn[column] = column;
    }
    int unlabeledColumnCount = cityCount;
    int labeledRowCount = 1;

    for (; ; ) {
        // Find a zero in an unlabeled column
        bool foundZero = false;
        for (int l = 0; l < unlabeledColumnCount; l++) {
            int column = unlabeledColumn[l];
            if (reducedCosts[column] == 0) {
                foundZero = true;

                // If the column is unassigned, we're done.
                if (fromCities[column] < 0) {
                    do {
                        int origin = pathOrigins[column];
                        fromCities[column] = origin;
                        int hold = toCities[origin];
                        toCities[origin] = column;
                        column = hold;
                    } while (column >= 0);
                    return;
                }

                // label the row corresponding to the column.
                labeledRow[labeledRowCount++] = fromCities[column];
                // remove label from column column
                unlabeledColumn[l] = unlabeledColumn[--unlabeledColumnCount];
                break;
            }
        }
        if (foundZero) {
            // Scan labeled rows
            int r = labeledRow[labeledRowCount - 1];
            for (int l = 0; l < unlabeledColumnCount; l++) {
                int column = unlabeledColumn[l];
                if (!IsAllowed(r, column))
                    continue;
                int reducedCost = distances[r][column] - u[r] - v[column];
                if (reducedCost < reducedCosts[column]) {
                    reducedCosts[column] = reducedCost;
                    pathOrigins[column] = r;
                }
            }
        } else {
            // Update the dual variables
            // Find minimum value.
            int minReducedCost = infinity;
            for (int l = 0; l < unlabeledColumnCount; l++) {
                int column = unlabeledColumn[l];
                if (reducedCosts[column] < minReducedCost)
                    minReducedCost = reducedCosts[column];
            }
            // Add minimum to dual variables of labeled rows
            for (int l = 0; l < labeledRowCount; l++) {
                int r = labeledRow[l];
                u[r] += minReducedCost;
            }
            // Subtract minimum from dual variables of labeled columns
            for (int column = 0; column < cityCount; column++) {
                if (reducedCosts[column] == 0)
                    v[column] -= minReducedCost;
                else
                    reducedCosts[column] -= minReducedCost;
            }
        }

    }
}

// Gets the starting point of the cycle of i length.
void AssignmentProblem::ComputeCycles() {
    bool* visited = new bool[cityCount];
    for (int i = 0; i < cityCount; i++) 
		visited[i] = false;
	this->cycles = std::vector<Cycle>();
    int cycleCount = 0;
    for (int i = 0; i < cityCount; i++) {
        if (visited[i])
            continue;
        cycleCount++;
        visited[i] = true;
        int next = toCities[i];
        int length = 1;
        int freeLength = constraintMap[i] > 0 ? 0 : 1;
        while (next != i) {
            visited[next] = true;
            length++;
            if (constraintMap[next] <= 0)
                freeLength++;
            next = toCities[next];
        }
        Cycle cycle;
        cycle.Length = length;
        cycle.FreeLength = freeLength;
        cycle.StartNode = i;
        this->cycles.push_back(cycle);
    }

	delete [] visited;

	sort(cycles.begin(), cycles.end());

    int minFreeLength = MAXINT;
    for (unsigned int i = 0; i < cycles.size(); i++)
        if (cycles[i].FreeLength < minFreeLength) {
            minCycle = i;
            minFreeLength = cycles[i].FreeLength;
        }
}

void AssignmentProblem::Patch(int from, int to, int from2, int to2) {
    patchedToCities[from] = to2;
    patchedFromCities[to2] = from;
    patchedToCities[from2] = to;
    patchedFromCities[to] = from2;
}

// Patches the cycles with the specified start cities using the
// Karp-Steele patch algorithm.
// Returns the cost of the patch.
__int64 AssignmentProblem::Patch(int startCity, int startCity2) {
    int bestLast = -1;
    int bestLast2 = -1;
    int last = startCity;
    int next = toCities[last];
    __int64 minPenalty = MAXLONG;
    while (next != startCity) {

        __int64 basePenalty = -distances[last][next];
        int last2 = startCity2;
        int next2 = toCities[last2];
        while (next2 != startCity2) {
            if (IsAllowed(last, next2) && IsAllowed(last2, next)) {
                __int64 penalty = basePenalty - distances[last2][next2]
                    + distances[last][next2] + distances[last2][next];
                if (penalty < minPenalty) {
					if (penalty == 0) {
                        Patch(last, next, last2, next2);
                        return 0;
					}
                    minPenalty = penalty;
                    bestLast = last;
                    bestLast2 = last2;
                }
            }
            last2 = next2;
            next2 = toCities[last2];
        }
        last = next;
        next = toCities[last];
    }

    if (bestLast < 0 || bestLast2 < 0)
        return infinity;
    Patch(bestLast, patchedToCities[bestLast], bestLast2, patchedToCities[bestLast2]);
    return minPenalty;
}

__int64 AssignmentProblem::Patch(Solver* solver) {
    patchedToCities = new int[cityCount];
	memcpy(patchedToCities, toCities, cityCount * sizeof(int));
    patchedFromCities = new int[cityCount];
	memcpy(patchedFromCities, fromCities, cityCount * sizeof(int));

    __int64 penalty = 0;
    __int64 maxPenalty = this->upperBound - this->lowerBound;
    for (int cycle = cycles.size() - 1; cycle > 0; --cycle) {
        int startCity = cycles[cycle].StartNode;
        int startCity2 = cycles[cycle - 1].StartNode;
        penalty += Patch(startCity, startCity2);
        if (penalty >= maxPenalty)
            break;
        if (solver != NULL)
            solver->ProcessMessages(false);
    }
    this->patchedValue = penalty == infinity ? infinity : this->lowerBound + penalty;
    return penalty;
}

BranchingInformation* AssignmentProblem::GetBranchingInformation() {

	// We can reuse the fixed buffer
	fixedBuffer[1] = this->getCycleCount();
	fixedBuffer[2] = (int)(lowerBound >> 32);
	fixedBuffer[3] = (int)(lowerBound & 0xffffffff);
    fixedBuffer[4] = exclusionsCount;

    // Find cycle with the least included branches.
    int minLength = MAXINT;
    int shortest = -1;
    for (int i = 0; i < cycles.size(); i++) {
        if (cycles[i].FreeLength < minLength) {
            shortest = i;
            minLength = cycles[i].FreeLength;
        }
    }

	fixedBuffer[5] = minLength;

	int *variableBuffer = new int[exclusionsCount + 2 * minLength];
	if (exclusionsCount > 0)
		memcpy(variableBuffer, exclusions, exclusionsCount * sizeof(int));
    int* childToCities = variableBuffer + exclusionsCount;
    int* childFromCities = variableBuffer + exclusionsCount + minLength;


    int last = cycles[shortest].StartNode;
    int next;
    int index = 0;
    do {
        next = toCities[last];
        if (constraintMap[last] <= 0) {
            childFromCities[index] = last;
            childToCities[index++] = next;
        }
        last = next;
    } while (last != cycles[shortest].StartNode);

	BranchingInformation *info = new BranchingInformation(this->cityCount, this->fixedBuffer, variableBuffer);
	this->fixedBuffer = NULL;
	return info;
}


Solver :: Solver()
{
    MPI_Comm_rank(MPI_COMM_WORLD, &rank);			// getting the rank of each process
    MPI_Comm_size(MPI_COMM_WORLD, &commsize);		// getting the count of all process
	distances = NULL;
	idle = NULL;
	currentBranchingInfo = NULL;
	bestCities = NULL;
	isRootThread = rank == 0;
}

Solver::~Solver() 
{
	if (distances != NULL) {
		if (distances[0] != NULL) {
			delete[] distances[0];
			distances[0] = NULL;
		}
		delete[] distances;
		distances = NULL;
	}
	if (rank == root) {
		if (bestCities != NULL) {
			delete[] bestCities;
			bestCities = NULL;
		}
	}
}

// Shared between root and other nodes
SolutionType Solver::Solve(AssignmentProblem* problem) {
    __int64 lowerBound = problem->Solve();
    if (lowerBound >= upperBound) {
        if (rank != root)
            problem->SendPrunedSolution(0);
        return PrunedSolution;
    } else if (lowerBound < upperBound && problem->getCycleCount() == 1) {
        if (rank != root)
            problem->SendExactSolution(0);
        return ExactSolution;
    } else {
        problem->Patch(rank == root ? this : NULL);
        if (rank == root)
            ProcessMessages(false);
		else {
            problem->SendPatchedSolution(0);
			BranchingInformation *info = problem->GetBranchingInformation();
			info->Send(0);
			delete info;
        }
        return PatchedSolution;
    }
}

// Root specific

// Gets the next problem. This method determines the search order.
AssignmentProblem* Solver::GetNextProblem() {
    AssignmentProblem* problem = currentBranchingInfo->GetProblem(distances, currentBranchingIndex, upperBound);
    currentBranchingIndex++;
    return problem;
}
void Solver::SendNextProblem(int destination) {
    currentBranchingInfo->SendProblem(currentBranchingIndex, upperBound, destination);
    currentBranchingIndex++;
}

bool Solver::MoreProblems(bool wait) {
	if (currentBranchingInfo->LowerBound < upperBound) {
	    if (currentBranchingIndex < currentBranchingInfo->getCount())
	        return true;
	}
    do {
        ProcessMessages(wait);
	    // Prune solved problems
	    while (solvedList.size() > 0 && solvedList.front()->LowerBound >= upperBound) {
			BranchingInformation *front = solvedList.front();
	        solvedList.pop_front();
			delete front;
	    }
	    if (solvedList.size() == 0) {
	        currentBranchingIndex = infinity;
	        continue;
	    }
		delete currentBranchingInfo;
	    currentBranchingInfo = solvedList.back();
	    currentBranchingIndex = 0;
	    solvedList.pop_back();
        return true;
    }
	while (wait && activeNodes > 0);
    return false;
}
void Solver::AddBranchingInformation(BranchingInformation* info) {
	list<BranchingInformation*>::iterator index;
	for (index = solvedList.begin(); index != solvedList.end() && *info < **index; index++)
        ;
    solvedList.insert(index, info);
}

void Solver::ProcessMessages(bool wait) { 
	int moreMessages;
	MPI_Iprobe(MPI_ANY_SOURCE, MpiSolutionMessage, MPI_COMM_WORLD, &moreMessages, &status);
    while (moreMessages || (wait && activeNodes > 0)) {
        if (~moreMessages) {
			MPI_Probe(MPI_ANY_SOURCE, MpiSolutionMessage, MPI_COMM_WORLD, &status);
        }

        // Receive solution
		int length = 4 + cityCount;
		int* buffer = new int[length];
		MPI_Recv(buffer, length, MPI_INT, status.MPI_SOURCE, MpiSolutionMessage, MPI_COMM_WORLD, &status);
		totalNodes++;

        SolutionType type = (SolutionType)buffer[0];
        switch (type) {
            case PrunedSolution:
                break;
            case ExactSolution:
            case PatchedSolution:
                __int64 value = ((__int64)buffer[2] << 32) + buffer[3];
                if (value < upperBound) {
                    upperBound = value;
					memcpy(bestCities, buffer + 4, cityCount * sizeof(int));
					printf("\n\r%ld", upperBound);
                }

                if (type == PatchedSolution) {
					BranchingInformation* info = BranchingInformation::Receive(cityCount, status.MPI_SOURCE);
                    AddBranchingInformation(info);
                }
                break;
        }

		// Try to keep the node busy right away.
        if (MoreProblems(false)) {
            SendNextProblem(status.MPI_SOURCE);
            // idle[status.MPI_SOURCE] = false;
            // activeNodes++;
		} else {
		activeNodes--;
        idle[status.MPI_SOURCE] = true;
		}

		MPI_Iprobe(MPI_ANY_SOURCE, MpiSolutionMessage, MPI_COMM_WORLD, &moreMessages, &status);
    }
}

AssignmentProblem *currentProblem;
void Solver::SolveRoot() {

	bestCities = new int[cityCount];

    // First, solve the initial problem.
    AssignmentProblem *first = new AssignmentProblem(cityCount, distances);
    __int64 lowerBound = first->Solve();
	totalNodes = 1;
    if (first->getCycleCount() == 1) {
        // Our first try is the best solution!
        first->GetCities(bestCities);
		delete first;
        upperBound = lowerBound;
    } else {
	    activeNodes = 0;
	    idle = new bool[commsize];
	    for (int i = 0; i < commsize; i++)
	        idle[i] = true;

	// Find an initial upper bound
        first->Patch(NULL);
        first->GetCities(bestCities);
        upperBound = first->getValue();

        // And create sub-problems
        currentBranchingInfo = first->GetBranchingInformation();
		currentBranchingIndex = 0;
		delete first;

        // Dispatch loop
        while (MoreProblems(true)) {
            // Process any waiting solution messages
            ProcessMessages(false);

            // Assign jobs to idle nodes
            for (int i = 1; i < commsize; i++) {
                if (!idle[i])
                    continue;
                if (!MoreProblems(false))
                    break;
                SendNextProblem(i);
                idle[i] = false;
                activeNodes++;
            }
            // Process any waiting solution messages
            ProcessMessages(false);

            // If we have more problems to do,
			// solve the next one.
            if (MoreProblems(false)) {
                currentProblem = GetNextProblem();
                SolutionType type = Solve(currentProblem);
				totalNodes++;
                switch (type) {
                    case PrunedSolution:
                        // Nothing to do
                        break;
                    case ExactSolution:
                    case PatchedSolution:
                        if (currentProblem->getValue() < upperBound) {
                            currentProblem->GetCities(bestCities);
                            upperBound = currentProblem->getValue();
							printf("\n\r%ld", upperBound);
                        }
                        if (type == PatchedSolution) {
                            BranchingInformation* info = currentProblem->GetBranchingInformation();
                            AddBranchingInformation(info);
                        }
                        break;
                }
            }
        }
		delete[] idle;
    }

    // Send empty problems to all nodes to signal that we're done.
    int zero = 0;
	for (int i = 0; i < commsize; i++) {
		if (i != root) {
			MPI_Send(&zero, 1, MPI_INT, i, MpiProblemMessage, MPI_COMM_WORLD);
		}
	}
}

void Solver::SolveNode() {
    for (; ; ) {
		AssignmentProblem* problem = AssignmentProblem::Receive(cityCount, distances, root);
        if (problem == NULL)
            break;
        Solve(problem);
		delete problem;
    }
}

// MPI-parallelized method of solving.
int Solver::Solve()
{
	MPI_Bcast(&cityCount, 1, MPI_INT, root, MPI_COMM_WORLD);
	if (rank != root) {
		distances = new int*[cityCount];
		int *buffer = new int[cityCount * cityCount];
		for (int i = 0; i < cityCount; i++)
			distances[i] = buffer + i * cityCount;
	}

	int result = MPI_Bcast(this->distances[0], cityCount * cityCount, MPI_INT, root, MPI_COMM_WORLD);

    upperBound = infinity;
    if (rank == root)
        SolveRoot();
    else
        SolveNode();
	return 0;
}

// Problem results output
void Solver::Finish(double time) {
}
